package workexp.alg.question.linklist;

import org.junit.Test;
import workexp.alg.env.ListNode;

import java.util.Stack;

/**
 * 给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
 *
 *  
 *
 * 示例 1：
 *
 *
 * 输入：head = [1,2,2,1]
 * 输出：true
 * 示例 2：
 *
 *
 * 输入：head = [1,2]
 * 输出：false
 *  
 *
 * 提示：
 *
 * 链表中节点数目在范围[1, 105] 内
 * 0 <= Node.val <= 9
 *  
 *
 * 进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
 *
 * 作者：力扣 (LeetCode)
 * 链接：https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnv1oc/
 * 来源：力扣（LeetCode）
 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 */
public class IsPalindrome {
    public boolean isPalindrome(ListNode head) {
        ListNode left,right;
        left=head;
        right=head;
        int size = 0;
        Stack<ListNode> stack = new Stack<>();
        if(right.next==null){
            return true;
        }else if(right.next.next==null){
            right=head.next;
            if(left.val==right.val){
                return true;
            }else{
                return false;
            }
        }
        while(right.next!=null&&right.next.next!=null){
            right=right.next.next;
            stack.push(left);
            left=left.next;
            size++;
        }
        //right.next==null right指针位于最后一个
        if(right.next!=null){
            //right不位于最后一个就要添加left的值
            stack.push(left);
        }
        while(!stack.empty()){
            ListNode tmp = stack.pop();
            ListNode curetor = left.next;
            left=left.next;
            if(curetor.val!=tmp.val){
                return false;
            }
        }

        return true;

    }

    @Test
    public void test(){
                ListNode head = ListNode.genList(new int[]{1,2,3,4,2,1});
//        ListNode head = ListNode.genList(new int[]{1,2,2,1});
//        ListNode head = ListNode.genList(new int[]{1,2});
//        ListNode head = ListNode.genList(new int[]{1,0,0});
        boolean res = isPalindrome(head);
        System.out.println(res);
    }
}
